package com.jack.leetcode.每日一题;

import java.util.*;

public class 二叉树的层次遍历 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        List<List<Integer>> result = new ArrayList<>();
        Map<Integer, List<Integer>> map = new TreeMap<>(Comparator.comparingInt(Integer::intValue));
        dfs(map, root, 0);
        map.forEach((k, v)->result.add(0, v));
        return result;
    }

    private void dfs(Map<Integer, List<Integer>> map, TreeNode root, int index){
        if(root == null){
            return;
        }
        List<Integer> integers = map.get(index);
        if(integers == null){
            integers = new ArrayList<>();
            integers.add(root.val);
            map.put(index, integers);
        }else{
            integers.add(root.val);
        }

        dfs(map, root.left, index + 1);
        dfs(map, root.right, index + 1);
    }

}
